// 使用链表实现队列

interface NodeInter<E> {
  e: E,
  next: NodeE | null
}

class NodeE<E = any> implements NodeInter<E> {
  public e: E
  public next: NodeE<E> | null

  constructor(e: E, next: NodeE | null = null) {
    this.e = e
    this.next = next
  }

  public toString() {
    return JSON.stringify(this.e)
  }
}

export class LinedListQueue<E> {
  private head: NodeE | null = null
  private tail: NodeE | null = null
  private size: number = 0

  /**
   *  getSize
   */
  public getSize() {
    return this.size
  }

  /**
   * isEmpty
   */
  public isEmpty() {
    return this.size === 0
  }

  /**
   * O(1)
   * enqueue
   */
  public enqueue(e: E) {
    // NOTE: 说明只有一个节点
    if (!this.tail) {
      this.tail = new NodeE(e)
      this.head = this.tail
    } else {
      this.tail.next = new NodeE(e)
      this.tail = this.tail.next
    }
    this.size++
  }

  /**
   * O(1)
   * dequeue
   */
  public dequeue(): E {
    if (this.isEmpty()) {
      throw new Error('queue is empty')
    }

    let rmNode = this.head
    this.head = this.head!.next
    rmNode!.next = null
    if (!this.head) {
      this.tail = null
    }
    this.size--
    return rmNode!.e
  }

  /**
   * getFront
   */
  public getFront() {
    if (this.isEmpty()) {
      throw new Error('queue is empty')
    }
    return this.head!.e
  }

}
